home *** CD-ROM | disk | FTP | other *** search
/ EuroCD 3 / EuroCD 3.iso / Programming / Python-1.4 / Demo / classes / bitvec.py next >
Encoding:
Python Source  |  1998-06-24  |  8.3 KB  |  333 lines
  1. #
  2. # this is a rather strict implementation of a bit vector class
  3. # it is accessed the same way as an array of python-ints, except
  4. # the value must be 0 or 1
  5. #
  6.  
  7. import sys; rprt = sys.stderr.write #for debugging
  8.  
  9. error = 'bitvec.error'
  10.  
  11.  
  12. def _check_value(value):
  13.     if type(value) != type(0) or not 0 <= value < 2:
  14.         raise error, 'bitvec() items must have int value 0 or 1'
  15.  
  16.  
  17. import math
  18.  
  19. def _compute_len(param):
  20.     mant, l = math.frexp(float(param))
  21.     bitmask = 1L << l
  22.     if bitmask <= param:
  23.         raise 'FATAL', '(param, l) = ' + `param, l`
  24.     while l:
  25.         bitmask = bitmask >> 1
  26.         if param & bitmask:
  27.             break
  28.         l = l - 1
  29.     return l
  30.  
  31.  
  32. def _check_key(len, key):
  33.     if type(key) != type(0):
  34.         raise TypeError, 'sequence subscript not int'
  35.     if key < 0:
  36.         key = key + len
  37.     if not 0 <= key < len:
  38.         raise IndexError, 'list index out of range'
  39.     return key
  40.  
  41. def _check_slice(len, i, j):
  42.     #the type is ok, Python already checked that
  43.     i, j = max(i, 0), min(len, j)
  44.     if i > j:
  45.         i = j
  46.     return i, j
  47.     
  48.  
  49. class BitVec:
  50.  
  51.     def __init__(self, *params):
  52.         self._data = 0L
  53.         self._len = 0
  54.         if not len(params):
  55.             pass
  56.         elif len(params) == 1:
  57.             param, = params
  58.             if type(param) == type([]):
  59.                 value = 0L
  60.                 bit_mask = 1L
  61.                 for item in param:
  62.                     # strict check
  63.                     #_check_value(item)
  64.                     if item:
  65.                         value = value | bit_mask
  66.                     bit_mask = bit_mask << 1
  67.                 self._data = value
  68.                 self._len = len(param)
  69.             elif type(param) == type(0L):
  70.                 if param < 0:
  71.                     raise error, 'bitvec() can\'t handle negative longs'
  72.                 self._data = param
  73.                 self._len = _compute_len(param)
  74.             else:
  75.                 raise error, 'bitvec() requires array or long parameter'
  76.         elif len(params) == 2:
  77.             param, length = params
  78.             if type(param) == type(0L):
  79.                 if param < 0:
  80.                     raise error, \
  81.                       'can\'t handle negative longs'
  82.                 self._data = param
  83.                 if type(length) != type(0):
  84.                     raise error, 'bitvec()\'s 2nd parameter must be int'
  85.                 computed_length = _compute_len(param)
  86.                 if computed_length > length:
  87.                     print 'warning: bitvec() value is longer than the lenght indicates, truncating value'
  88.                     self._data = self._data & \
  89.                           ((1L << length) - 1)
  90.                 self._len = length
  91.             else:
  92.                 raise error, 'bitvec() requires array or long parameter'
  93.         else:
  94.             raise error, 'bitvec() requires 0 -- 2 parameter(s)'
  95.  
  96.         
  97.     def append(self, item):
  98.         #_check_value(item)
  99.         #self[self._len:self._len] = [item]
  100.         self[self._len:self._len] = \
  101.               BitVec(long(not not item), 1)
  102.  
  103.         
  104.     def count(self, value):
  105.         #_check_value(value)
  106.         if value:
  107.             data = self._data
  108.         else:
  109.             data = (~self)._data
  110.         count = 0
  111.         while data:
  112.             data, count = data >> 1, count + (data & 1 != 0)
  113.         return count
  114.  
  115.  
  116.     def index(self, value):
  117.         #_check_value(value):
  118.         if value:
  119.             data = self._data
  120.         else:
  121.             data = (~self)._data
  122.         index = 0
  123.         if not data:
  124.             raise ValueError, 'list.index(x): x not in list'
  125.         while not (data & 1):
  126.             data, index = data >> 1, index + 1
  127.         return index
  128.  
  129.  
  130.     def insert(self, index, item):
  131.         #_check_value(item)
  132.         #self[index:index] = [item]
  133.         self[index:index] = BitVec(long(not not item), 1)
  134.  
  135.  
  136.     def remove(self, value):
  137.         del self[self.index(value)]
  138.  
  139.  
  140.     def reverse(self):
  141.         #ouch, this one is expensive!
  142.         #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i]
  143.         data, result = self._data, 0L
  144.         for i in range(self._len):
  145.             if not data:
  146.                 result = result << (self._len - i)
  147.                 break
  148.             result, data = (result << 1) | (data & 1), data >> 1
  149.         self._data = result
  150.  
  151.         
  152.     def sort(self):
  153.         c = self.count(1)
  154.         self._data = ((1L << c) - 1) << (self._len - c)
  155.  
  156.  
  157.     def copy(self):
  158.         return BitVec(self._data, self._len)
  159.  
  160.  
  161.     def seq(self):
  162.         result = []
  163.         for i in self:
  164.             result.append(i)
  165.         return result
  166.         
  167.  
  168.     def __repr__(self):
  169.         ##rprt('<bitvec class instance object>.' + '__repr__()\n')
  170.         return 'bitvec' + `self._data, self._len`
  171.  
  172.     def __cmp__(self, other, *rest):
  173.         #rprt(`self`+'.__cmp__'+`(other, ) + rest`+'\n')
  174.         if type(other) != type(self):
  175.             other = apply(bitvec, (other, ) + rest)
  176.         #expensive solution... recursive binary, with slicing
  177.         length = self._len
  178.         if length == 0 or other._len == 0:
  179.             return cmp(length, other._len)
  180.         if length != other._len:
  181.             min_lenght = min(length, other._len)
  182.             return cmp(self[:min_length], other[:min_length]) or \
  183.                   cmp(self[min_length:], other[min_length:])
  184.         #the lengths are the same now...
  185.         if self._data == other._data:
  186.             return 0
  187.         if length == 1:
  188.             return cmp(self[0], other[0])
  189.         else:
  190.             length = length >> 1
  191.             return cmp(self[:length], other[:length]) or \
  192.                   cmp(self[length:], other[length:])
  193.         
  194.  
  195.     def __len__(self):
  196.         #rprt(`self`+'.__len__()\n')
  197.         return self._len
  198.  
  199.     def __getitem__(self, key):
  200.         #rprt(`self`+'.__getitem__('+`key`+')\n')
  201.         key = _check_key(self._len, key)
  202.         return self._data & (1L << key) != 0
  203.  
  204.     def __setitem__(self, key, value):
  205.         #rprt(`self`+'.__setitem__'+`key, value`+'\n')
  206.         key = _check_key(self._len, key)
  207.         #_check_value(value)
  208.         if value:
  209.             self._data = self._data | (1L << key)
  210.         else:
  211.             self._data = self._data & ~(1L << key)
  212.  
  213.     def __delitem__(self, key):
  214.         #rprt(`self`+'.__delitem__('+`key`+')\n')
  215.         key = _check_key(self._len, key)
  216.         #el cheapo solution...
  217.         self._data = self[:key]._data | self[key+1:]._data >> key
  218.         self._len = self._len - 1
  219.  
  220.     def __getslice__(self, i, j):
  221.         #rprt(`self`+'.__getslice__'+`i, j`+'\n')
  222.         i, j = _check_slice(self._len, i, j)
  223.         if i >= j:
  224.             return BitVec(0L, 0)
  225.         if i:
  226.             ndata = self._data >> i
  227.         else:
  228.             ndata = self._data
  229.         nlength = j - i
  230.         if j != self._len:
  231.             #we'll have to invent faster variants here
  232.             #e.g. mod_2exp
  233.             ndata = ndata & ((1L << nlength) - 1)
  234.         return BitVec(ndata, nlength)
  235.  
  236.     def __setslice__(self, i, j, sequence, *rest):
  237.         #rprt(`self`+'.__setslice__'+`(i, j, sequence) + rest`+'\n')
  238.         i, j = _check_slice(self._len, i, j)
  239.         if type(sequence) != type(self):
  240.             sequence = apply(bitvec, (sequence, ) + rest)
  241.         #sequence is now of our own type
  242.         ls_part = self[:i]
  243.         ms_part = self[j:]
  244.         self._data = ls_part._data | \
  245.               ((sequence._data | \
  246.               (ms_part._data << sequence._len)) << ls_part._len)
  247.         self._len = self._len - j + i + sequence._len
  248.  
  249.     def __delslice__(self, i, j):
  250.         #rprt(`self`+'.__delslice__'+`i, j`+'\n')
  251.         i, j = _check_slice(self._len, i, j)
  252.         if i == 0 and j == self._len:
  253.             self._data, self._len = 0L, 0
  254.         elif i < j:
  255.             self._data = self[:i]._data | (self[j:]._data >> i)
  256.             self._len = self._len - j + i
  257.  
  258.     def __add__(self, other):
  259.         #rprt(`self`+'.__add__('+`other`+')\n')
  260.         retval = self.copy()
  261.         retval[self._len:self._len] = other
  262.         return retval
  263.  
  264.     def __mul__(self, multiplier):
  265.         #rprt(`self`+'.__mul__('+`multiplier`+')\n')
  266.         if type(multiplier) != type(0):
  267.             raise TypeError, 'sequence subscript not int'
  268.         if multiplier <= 0:
  269.             return BitVec(0L, 0)
  270.         elif multiplier == 1:
  271.             return self.copy()
  272.         #handle special cases all 0 or all 1...
  273.         if self._data == 0L:
  274.             return BitVec(0L, self._len * multiplier)
  275.         elif (~self)._data == 0L:
  276.             return ~BitVec(0L, self._len * multiplier)
  277.         #otherwise el cheapo again...
  278.         retval = BitVec(0L, 0)
  279.         while multiplier:
  280.             retval, multiplier = retval + self, multiplier - 1
  281.         return retval
  282.  
  283.     def __and__(self, otherseq, *rest):
  284.         #rprt(`self`+'.__and__'+`(otherseq, ) + rest`+'\n')
  285.         if type(otherseq) != type(self):
  286.             otherseq = apply(bitvec, (otherseq, ) + rest)
  287.         #sequence is now of our own type
  288.         return BitVec(self._data & otherseq._data, \
  289.               min(self._len, otherseq._len))
  290.  
  291.  
  292.     def __xor__(self, otherseq, *rest):
  293.         #rprt(`self`+'.__xor__'+`(otherseq, ) + rest`+'\n')
  294.         if type(otherseq) != type(self):
  295.             otherseq = apply(bitvec, (otherseq, ) + rest)
  296.         #sequence is now of our own type
  297.         return BitVec(self._data ^ otherseq._data, \
  298.               max(self._len, otherseq._len))
  299.  
  300.  
  301.     def __or__(self, otherseq, *rest):
  302.         #rprt(`self`+'.__or__'+`(otherseq, ) + rest`+'\n')
  303.         if type(otherseq) != type(self):
  304.             otherseq = apply(bitvec, (otherseq, ) + rest)
  305.         #sequence is now of our own type
  306.         return BitVec(self._data | otherseq._data, \
  307.               max(self._len, otherseq._len))
  308.  
  309.  
  310.     def __invert__(self):
  311.         #rprt(`self`+'.__invert__()\n')
  312.         return BitVec(~self._data & ((1L << self._len) - 1), \
  313.               self._len)
  314.  
  315.     def __coerce__(self, otherseq, *rest):
  316.         #needed for *some* of the arithmetic operations
  317.         #rprt(`self`+'.__coerce__'+`(otherseq, ) + rest`+'\n')
  318.         if type(otherseq) != type(self):
  319.             otherseq = apply(bitvec, (otherseq, ) + rest)
  320.         return self, otherseq
  321.  
  322.     def __int__(self):
  323.         return int(self._data)
  324.  
  325.     def __long__(self):
  326.         return long(self._data)
  327.  
  328.     def __float__(self):
  329.         return float(self._data)
  330.  
  331.  
  332. bitvec = BitVec
  333.